package com.formula.datastructure.exercise.sort.basic;

import com.formula.datastructure.util.DataUtil;

/**
 * 心得体会:
 * #3 画图可以快速推导算法
 * #4
 */
public class InsertSort {
    /**
     * 改进记录:
     * #1
     * #2
     */
    public Integer[] sort(Integer[] input) {
        for (int i = 1; i < input.length; i++) {
            Integer temp = input[i];
            // #2 如果这里不单独保存idx, 可以写int j, 但idx更好理解
            int idx = i;
            // compare
            for (int j = i - 1; j >= 0; j--) {
                // #1 不是拿input[i]去比, 是用temp去比
                if (temp < input[j]) {
                    input[j + 1] = input[j];
                    idx = j;
                } else { // i >= j
                    break;
                }
            }
            // #4 如果用idx可以更方便比较是否需要替换
            if (idx != i) {
                input[idx] = temp;
            }
        }
        return input;
    }

    public static void main(String[] args) {
        InsertSort insert = new InsertSort();
        Integer[] array = DataUtil.genUniqueArray(12, 50);
        DataUtil.printArray(array);
        DataUtil.printArray(insert.sort(array));
    }
}
